// https://leetcode.cn/problems/word-pattern/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 记录字符和单词最近出现的位置
// 2. 同构的字符和单词应有相同的位置记录
// 3. 位置不同说明映射关系不一致
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <unordered_map>

class Solution 
{
public:
    bool wordPattern(string pattern, string s) 
    {
        vector<string> vs;

        stringstream ss(s);
        string word;
        while (ss >> word)
        {
            vs.push_back(word);
        }

        if (pattern.size() != vs.size())  return false;

        unordered_map<char, string> c2s;
        unordered_map<string, char> s2c;
        for (int i = 0 ; i < pattern.size() ; i++)
        {
            char a = pattern[i]; string b = vs[i];
            if (c2s.count(a) > 0 && c2s[a] != b)
            {
                return false;
            }
            if (s2c.count(b) > 0 && s2c[b] != a)
            {
                return false;
            }        
            c2s[a] = b;
            s2c[b] = a;
        }

        return true;
    }
};

int main()
{
    string pattern1 = "abba", pattern2 = "abba", pattern3 = "aaaa";
    string s1 = "dog cat cat dog", s2 = "dog cat cat fish", s3 = "dog cat cat dog";

    Solution sol;

    cout << (sol.wordPattern(pattern1, s1) == 1 ? "True" : "False") << endl;
    cout << (sol.wordPattern(pattern2, s2) == 1 ? "True" : "False") << endl;
    cout << (sol.wordPattern(pattern3, s3) == 1 ? "True" : "False") << endl;


    return 0;
}